SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Hidden subgroup problem</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Hidden subgroup problem</span></span>

</h1>

</header>

<p>

The <b>hidden subgroup problem</b> (<b>HSP</b>) is a topic of research in <a href="Mathematics" title="Mathematics">mathematics</a> and <a href="Theoretical_computer_science" title="Theoretical computer science">theoretical computer science</a>. The framework captures problems such as <a href="Integer_factorization" title="Integer factorization">factoring</a>, <a href="Discrete_logarithm" title="Discrete logarithm">discrete logarithm</a>, <a href="Graph_isomorphism_problem" title="Graph isomorphism problem">graph isomorphism</a>, and the <a href="Shortest_vector_problem" class="mw-redirect" title="Shortest vector problem">shortest vector problem</a>. This makes it especially important in the theory of <a href="Quantum_computing" title="Quantum computing">quantum computing</a> because <a href="Shor's_algorithm" title="Shor's algorithm">Shor's algorithms</a> for factoring and finding discrete logarithms in <a href="Quantum_computing" title="Quantum computing">quantum computing</a> are instances of the hidden subgroup problem for <a href="Finite_abelian_group" class="mw-redirect" title="Finite abelian group">finite abelian groups</a>, while the other problems correspond to finite groups that are not abelian.

</p>

<div class="mw-heading mw-heading2"><h2 id="Problem_statement">Problem statement</h2></div>

<p>Given a <a href="Group_(mathematics)" title="Group (mathematics)">group</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math></span><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"></span>, a <a href="Subgroup" title="Subgroup">subgroup</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H\leq G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H\leq G}</annotation>

</semantics>

</math></span><img src="./c9c017471513c8b1345c68cf521c2a7c451bad4e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.989ex; height:2.343ex;" alt="{\displaystyle H\leq G}" loading="lazy"></span>, and a set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math></span><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"></span>, we say a function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:G\to X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:G\to X}</annotation>

</semantics>

</math></span><img src="./68d35e48aa68490d5fb7f05e7cc0cd7e5b0484fb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.637ex; height:2.509ex;" alt="{\displaystyle f:G\to X}" loading="lazy"></span> <b>hides</b> the subgroup <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math></span><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"></span> if for all <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{1},g_{2}\in G,f(g_{1})=f(g_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{1},g_{2}\in G,f(g_{1})=f(g_{2})}</annotation>

</semantics>

</math></span><img src="./f443add7b92721cc06321938babbbcbbe6ad8724.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.663ex; height:2.843ex;" alt="{\displaystyle g_{1},g_{2}\in G,f(g_{1})=f(g_{2})}" loading="lazy"></span> if and only if <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{1}H=g_{2}H}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g_{1}H=g_{2}H}</annotation>

</semantics>

</math></span><img src="./bdc4c4347ad22a16c2d269173f33bf9efd85f8d9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.552ex; height:2.509ex;" alt="{\displaystyle g_{1}H=g_{2}H}" loading="lazy"></span>. Equivalently, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math></span><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"></span> is constant on each <a href="Cosets" class="mw-redirect" title="Cosets">coset</a> of <i>H</i>, while it is different between the different cosets of <i>H</i>.

</p><p><b>Hidden subgroup problem</b>: Let <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math></span><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"></span> be a group, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math></span><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"></span> a finite set, and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:G\to X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:G\to X}</annotation>

</semantics>

</math></span><img src="./68d35e48aa68490d5fb7f05e7cc0cd7e5b0484fb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.637ex; height:2.509ex;" alt="{\displaystyle f:G\to X}" loading="lazy"></span> a function that hides a subgroup <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H\leq G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H\leq G}</annotation>

</semantics>

</math></span><img src="./c9c017471513c8b1345c68cf521c2a7c451bad4e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.989ex; height:2.343ex;" alt="{\displaystyle H\leq G}" loading="lazy"></span>. The function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math></span><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"></span> is given via an <a href="Oracle_machine" title="Oracle machine">oracle</a>, which uses <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log |G|+\log |X|)}">

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log |G|+\log |X|)}</annotation>

</semantics>

</math></span><img src="./eacfc214496c5d2b2b0d59f6205f808fc7c83f5f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.535ex; height:2.843ex;" alt="{\displaystyle O(\log |G|+\log |X|)}" loading="lazy"></span> bits. Using information gained from evaluations of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math></span><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"></span> via its oracle, determine a <a href="Generator_(mathematics)" title="Generator (mathematics)">generating set</a> for <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math></span><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"></span>.

</p><p>A special case is when <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math></span><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"></span> is a group and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math></span><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"></span> is a <a href="Group_homomorphism" title="Group homomorphism">group homomorphism</a> in which case <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math></span><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"></span> corresponds to the <a href="Kernel_(algebra)" title="Kernel (algebra)">kernel</a> of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math></span><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"></span>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Motivation">Motivation</h2></div>

<p>The hidden subgroup problem is especially important in the theory of <a href="Quantum_computer" class="mw-redirect" title="Quantum computer">quantum computing</a> for the following reasons.

</p>

<ul><li><a href="Shor's_algorithm" title="Shor's algorithm">Shor's algorithm</a> for factoring and for finding <a href="Discrete_logarithm" title="Discrete logarithm">discrete logarithms</a> (as well as several of its extensions) relies on the ability of quantum computers to solve the HSP for <a href="Finite_abelian_group" class="mw-redirect" title="Finite abelian group">finite abelian groups</a>.</li>

<li>The existence of efficient <a href="Quantum_algorithm" title="Quantum algorithm">quantum algorithms</a> for HSPs for certain <a href="Non-abelian_group" title="Non-abelian group">non-abelian groups</a> would imply efficient quantum algorithms for two major problems: the <a href="Graph_isomorphism_problem" title="Graph isomorphism problem">graph isomorphism problem</a> and certain <a href="Shortest_vector_problem" class="mw-redirect" title="Shortest vector problem">shortest vector problems</a> (SVPs) in lattices. More precisely, an efficient quantum algorithm for the HSP for the <a href="Symmetric_group" title="Symmetric group">symmetric group</a> would give a quantum algorithm for the graph isomorphism.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> An efficient quantum algorithm for the HSP for the <a href="Dihedral_group" title="Dihedral group">dihedral group</a> would give a quantum algorithm for the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \operatorname {poly} (n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {poly} (n)}</annotation>

</semantics>

</math></span><img src="./9a487cceee40f7b817a279dd1ebb214770edc07c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.533ex; height:2.843ex;" alt="{\displaystyle \operatorname {poly} (n)}" loading="lazy"></span> unique SVP.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Quantum_algorithms">Quantum algorithms</h2></div>

<p>There is an efficient <a href="Quantum_algorithm" title="Quantum algorithm">quantum algorithm</a> for solving HSP over finite <a href="Abelian_group" title="Abelian group">abelian groups</a> in time polynomial in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log |G|}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log |G|}</annotation>

</semantics>

</math></span><img src="./8196572d3d687b438d27fd91b48bc34f06e6c2c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.479ex; height:2.843ex;" alt="{\displaystyle \log |G|}" loading="lazy"></span>. For arbitrary groups, it is known that the hidden subgroup problem is solvable using a polynomial number of evaluations of the oracle.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> However, the circuits that implement this may be exponential in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log |G|}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log |G|}</annotation>

</semantics>

</math></span><img src="./8196572d3d687b438d27fd91b48bc34f06e6c2c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.479ex; height:2.843ex;" alt="{\displaystyle \log |G|}" loading="lazy"></span>, making the algorithm not efficient overall; efficient algorithms must be polynomial in the number of oracle evaluations and running time. The existence of such an algorithm for arbitrary groups is open. Quantum polynomial time algorithms exist for certain subclasses of groups, such as semi-direct products of some <a href="Abelian_group" title="Abelian group">abelian groups</a>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Algorithm_for_abelian_groups">Algorithm for abelian groups</h3></div>

<p>The algorithm for abelian groups uses <a href="Representation_theory" title="Representation theory">representations</a>, i.e. homomorphisms from <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math></span><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"></span> to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {GL} _{k}(\mathbb {C} )}">

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {GL} _{k}(\mathbb {C} )}</annotation>

</semantics>

</math></span><img src="./1be71c7e53a9e5a666de0b5d09c75eff8e15b76c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.853ex; height:2.843ex;" alt="{\displaystyle \mathrm {GL} _{k}(\mathbb {C} )}" loading="lazy"></span>, the <a href="General_linear_group" title="General linear group">general linear group</a> over the <a href="Complex_number" title="Complex number">complex numbers</a>. A representation is irreducible if it cannot be expressed as the <a href="Direct_product" title="Direct product">direct product</a> of two or more representations of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math></span><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"></span>. For an abelian group, all the <a href="Irreducible_representation" title="Irreducible representation">irreducible representations</a> are the <a href="Character_theory" title="Character theory">characters</a>, which are the representations of dimension one; there are no irreducible representations of larger dimension for abelian groups.

</p>

<div class="mw-heading mw-heading4"><h4 id="Defining_the_quantum_fourier_transform">Defining the quantum fourier transform</h4></div>

<p>The <a href="Quantum_Fourier_transform" title="Quantum Fourier transform">quantum fourier transform</a> can be defined in terms of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {Z} _{N}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {Z} _{N}}</annotation>

</semantics>

</math></span><img src="./0127f972fd0a0816cc91210701b1159ae2831e42.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.112ex; height:2.509ex;" alt="{\displaystyle \mathrm {Z} _{N}}" loading="lazy"></span>, the additive <a href="Cyclic_group" title="Cyclic group">cyclic group</a> of order <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math></span><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"></span>. Introducing the character<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \chi _{j}(k)=\omega _{N}^{jk}=e^{2\pi i{\frac {jk}{N}}},}">

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

<msup>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \chi _{j}(k)=\omega _{N}^{jk}=e^{2\pi i{\frac {jk}{N}}},}</annotation>

</semantics>

</math></span></span>the quantum fourier transform has the definition of<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{N}|j\rangle ={\frac {1}{\sqrt {N}}}\sum _{k=0}^{N}\chi _{j}(k)|k\rangle .}">

<msub>

</mrow>

</msub>

</mrow>

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{N}|j\rangle ={\frac {1}{\sqrt {N}}}\sum _{k=0}^{N}\chi _{j}(k)|k\rangle .}</annotation>

</semantics>

</math></span></span>Furthermore, we define <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\chi _{j}\rangle =F_{N}|j\rangle }">

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |\chi _{j}\rangle =F_{N}|j\rangle }</annotation>

</semantics>

</math></span><img src="./cf17443bbf543367b8baed93de7dae4afc651665.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:12.71ex; height:3.009ex;" alt="{\displaystyle |\chi _{j}\rangle =F_{N}|j\rangle }" loading="lazy"></span>. Any finite abelian group can be written as the direct product of multiple cyclic groups <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {Z} _{N_{1}}\times \mathrm {Z} _{N_{2}}\times \ldots \times \mathrm {Z} _{N_{m}}}">

<msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {Z} _{N_{1}}\times \mathrm {Z} _{N_{2}}\times \ldots \times \mathrm {Z} _{N_{m}}}</annotation>

</semantics>

</math></span><img src="./a5c02f910286179c65819589c1383bd92e3fa544.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:23.159ex; height:2.843ex;" alt="{\displaystyle \mathrm {Z} _{N_{1}}\times \mathrm {Z} _{N_{2}}\times \ldots \times \mathrm {Z} _{N_{m}}}" loading="lazy"></span>. On a quantum computer, this is represented as the tensor product of multiple registers of dimensions <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{1},N_{2},\ldots ,N_{m}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{1},N_{2},\ldots ,N_{m}}</annotation>

</semantics>

</math></span><img src="./389832e2c243735db4329290039fc9dc424baa3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.594ex; height:2.509ex;" alt="{\displaystyle N_{1},N_{2},\ldots ,N_{m}}" loading="lazy"></span> respectively, and the overall quantum fourier transform is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{N_{1}}\otimes F_{N_{2}}\otimes \ldots \otimes F_{N_{m}}}">

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{N_{1}}\otimes F_{N_{2}}\otimes \ldots \otimes F_{N_{m}}}</annotation>

</semantics>

</math></span><img src="./3234c69040dd1c910ed50c09e48eb3045c9cac86.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:23.382ex; height:2.843ex;" alt="{\displaystyle F_{N_{1}}\otimes F_{N_{2}}\otimes \ldots \otimes F_{N_{m}}}" loading="lazy"></span>.

</p>

<div class="mw-heading mw-heading4"><h4 id="Procedure">Procedure</h4></div>

<p>The set of characters of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math></span><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"></span> forms a group <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\widehat {G}}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\widehat {G}}}</annotation>

</semantics>

</math></span><img src="./3257528da95b4ab702b74241ff5356d688de2ce0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:3.009ex;" alt="{\displaystyle {\widehat {G}}}" loading="lazy"></span> called the <a href="Pontryagin_duality" title="Pontryagin duality">dual group</a> of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math></span><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"></span>. We also have a subgroup <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H^{\perp }\leq {\widehat {G}}}">

<msup>

</mrow>

</msup>

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H^{\perp }\leq {\widehat {G}}}</annotation>

</semantics>

</math></span><img src="./eb8ec4649299cb6e190014be702121d62c2fe63f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:8.539ex; height:3.176ex;" alt="{\displaystyle H^{\perp }\leq {\widehat {G}}}" loading="lazy"></span> of size <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |G|/|H|}">

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |G|/|H|}</annotation>

</semantics>

</math></span><img src="./03cd110506d8be74e70cb1dcb331f4971c099a26.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.64ex; height:2.843ex;" alt="{\displaystyle |G|/|H|}" loading="lazy"></span> defined by<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H^{\perp }=\{\chi _{g}:\chi _{g}(h)=1{\text{ for all }}h\in H\}}">

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H^{\perp }=\{\chi _{g}:\chi _{g}(h)=1{\text{ for all }}h\in H\}}</annotation>

</semantics>

</math></span></span>For each iteration of the algorithm, the quantum circuit outputs an element <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g\in G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g\in G}</annotation>

</semantics>

</math></span><img src="./b1be73903416a0dd94b8cbc2268ce480810c0e62.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.783ex; height:2.509ex;" alt="{\displaystyle g\in G}" loading="lazy"></span> corresponding to a character <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \chi _{g}\in H^{\perp }}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \chi _{g}\in H^{\perp }}</annotation>

</semantics>

</math></span><img src="./d32a93c0d1f098f77377ba1e658b296da0376b9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.931ex; height:3.343ex;" alt="{\displaystyle \chi _{g}\in H^{\perp }}" loading="lazy"></span>, and since <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \chi _{g}(h)={1}}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \chi _{g}(h)={1}}</annotation>

</semantics>

</math></span><img src="./1e7089c0a454505e858f100d4ea5b68cd3d63192.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:9.886ex; height:3.009ex;" alt="{\displaystyle \chi _{g}(h)={1}}" loading="lazy"></span> for all <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h\in H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h\in H}</annotation>

</semantics>

</math></span><img src="./675a79e26028d91d97f4e2ce279c314b0f194c1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.243ex; height:2.176ex;" alt="{\displaystyle h\in H}" loading="lazy"></span>, it helps to pin down what <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math></span><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"></span> is.

</p><p>The algorithm is as follows:

</p>

<ol><li>Start with the state <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |0\rangle |0\rangle }">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |0\rangle |0\rangle }</annotation>

</semantics>

</math></span><img src="./dae9327529c312e8de8a8c98bcdd5935bdc34401.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.428ex; height:2.843ex;" alt="{\displaystyle |0\rangle |0\rangle }" loading="lazy"></span>, where the left register's basis states are each element of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math></span><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"></span>, and the right register's basis states are each element of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math></span><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"></span>.</li>

<li>Create a superposition among the basis states of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math></span><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"></span> in the left register, leaving the state <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle {\frac {1}{\sqrt {|G|}}}\sum _{g\in G}|g\rangle |0\rangle }">

<mfrac>

<msqrt>

</mrow>

</mrow>

</msqrt>

</mfrac>

</mrow>

</mrow>

</munder>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle {\frac {1}{\sqrt {|G|}}}\sum _{g\in G}|g\rangle |0\rangle }</annotation>

</semantics>

</math></span><img src="./fc8027d03cd274cadbd3cf9cf50c9ce9575be28c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:16.705ex; height:4.509ex;" alt="{\textstyle {\frac {1}{\sqrt {|G|}}}\sum _{g\in G}|g\rangle |0\rangle }" loading="lazy"></span>.</li>

<li>Query the function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math></span><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"></span>. The state afterwards is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle {\frac {1}{\sqrt {|G|}}}\sum _{g\in G}|g\rangle |f(g)\rangle }">

<mfrac>

<msqrt>

</mrow>

</mrow>

</msqrt>

</mfrac>

</mrow>

</mrow>

</munder>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle {\frac {1}{\sqrt {|G|}}}\sum _{g\in G}|g\rangle |f(g)\rangle }</annotation>

</semantics>

</math></span><img src="./1807c9e0ad4fbd342611e62625b4c2bdf4e3bc7f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:19.746ex; height:4.509ex;" alt="{\textstyle {\frac {1}{\sqrt {|G|}}}\sum _{g\in G}|g\rangle |f(g)\rangle }" loading="lazy"></span>.</li>

<li>Measure the output register. This gives some <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(s)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(s)}</annotation>

</semantics>

</math></span><img src="./644b5a9d19add61f865991dcf152e46e6428ff27.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.178ex; height:2.843ex;" alt="{\displaystyle f(s)}" loading="lazy"></span> for some <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s\in G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s\in G}</annotation>

</semantics>

</math></span><img src="./f3669b548485e062ed616d490e37d9294f6e57dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.758ex; height:2.176ex;" alt="{\displaystyle s\in G}" loading="lazy"></span>, and collapses the state to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle {\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|s+h\rangle |f(s)\rangle }">

<mfrac>

<msqrt>

</mrow>

</mrow>

</msqrt>

</mfrac>

</mrow>

</mrow>

</munder>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle {\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|s+h\rangle |f(s)\rangle }</annotation>

</semantics>

</math></span><img src="./c65f42d83bcc236bd74484ed2a03e46130052a70.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:24.367ex; height:4.509ex;" alt="{\textstyle {\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|s+h\rangle |f(s)\rangle }" loading="lazy"></span> because <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math></span><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"></span> has the same value for each element of the coset <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s+{H}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s+{H}}</annotation>

</semantics>

</math></span><img src="./54dffb9378dd39f343a26c3e6b1f03161286ec2b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.994ex; height:2.343ex;" alt="{\displaystyle s+{H}}" loading="lazy"></span>. We discard the output register to get <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle {\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|s+h\rangle }">

<mfrac>

<msqrt>

</mrow>

</mrow>

</msqrt>

</mfrac>

</mrow>

</mrow>

</munder>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle {\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|s+h\rangle }</annotation>

</semantics>

</math></span><img src="./62247cec2e9dd8417238bd947553be8b3cd1cd45.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:18.637ex; height:4.509ex;" alt="{\textstyle {\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|s+h\rangle }" loading="lazy"></span>.</li>

<li>Perform the quantum fourier transform, getting the state <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle {\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|\chi _{s+h}\rangle }">

<mfrac>

<msqrt>

</mrow>

</mrow>

</msqrt>

</mfrac>

</mrow>

</mrow>

</munder>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle {\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|\chi _{s+h}\rangle }</annotation>

</semantics>

</math></span><img src="./8b8d8570f892dda4bce8eaafe154b0999b1edf41.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:18.051ex; height:4.509ex;" alt="{\textstyle {\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|\chi _{s+h}\rangle }" loading="lazy"></span>.</li>

<li>This state is equal to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle {\sqrt {\frac {|H|}{|G|}}}\sum _{\chi _{g}\in H^{\perp }}\chi _{g}(s)|g\rangle }">

<msqrt>

<mfrac>

<mrow>

</mrow>

</mrow>

<mrow>

</mrow>

</mrow>

</mfrac>

</msqrt>

</mrow>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle {\sqrt {\frac {|H|}{|G|}}}\sum _{\chi _{g}\in H^{\perp }}\chi _{g}(s)|g\rangle }</annotation>

</semantics>

</math></span><img src="./60c74e07e98b37fd968deb938bbc44abaeae9781.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:22.658ex; height:6.343ex;" alt="{\textstyle {\sqrt {\frac {|H|}{|G|}}}\sum _{\chi _{g}\in H^{\perp }}\chi _{g}(s)|g\rangle }" loading="lazy"></span>, which can be measured to learn information about <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math></span><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"></span>.</li>

<li>Repeat until <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math></span><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"></span> (or a generating set for <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math></span><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"></span>) is determined.</li></ol>

<p>The state in step 5 is equal to the state in step 6 because of the following:<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}{\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|\chi _{s+h}\rangle &={\frac {1}{\sqrt {|H||G|}}}\sum _{h\in H}\sum _{g\in G}\chi _{s+h}(g)|g\rangle \\&={\frac {1}{\sqrt {|H||G|}}}\sum _{g\in G}\chi _{s}(g)\sum _{h\in H}\chi _{h}(g)|g\rangle \\&={\frac {1}{\sqrt {|H||G|}}}\sum _{g\in G}\chi _{g}(s)\left(\sum _{h\in H}\chi _{g}(h)\right)|g\rangle \\&={\sqrt {\frac {|H|}{|G|}}}\sum _{\chi _{g}\in H^{\perp }}\chi _{g}(s)|g\rangle \end{aligned}}}">

<mtr>

<mtd>

<mfrac>

<msqrt>

</mrow>

</mrow>

</msqrt>

</mfrac>

</mrow>

</mrow>

</munder>

</mrow>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<mfrac>

<msqrt>

</mrow>

</mrow>

</mrow>

</mrow>

</msqrt>

</mfrac>

</mrow>

</mrow>

</munder>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mfrac>

<msqrt>

</mrow>

</mrow>

</mrow>

</mrow>

</msqrt>

</mfrac>

</mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mfrac>

<msqrt>

</mrow>

</mrow>

</mrow>

</mrow>

</msqrt>

</mfrac>

</mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<mrow>

<mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msqrt>

<mfrac>

<mrow>

</mrow>

</mrow>

<mrow>

</mrow>

</mrow>

</mfrac>

</msqrt>

</mrow>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|\chi _{s+h}\rangle &={\frac {1}{\sqrt {|H||G|}}}\sum _{h\in H}\sum _{g\in G}\chi _{s+h}(g)|g\rangle \\&={\frac {1}{\sqrt {|H||G|}}}\sum _{g\in G}\chi _{s}(g)\sum _{h\in H}\chi _{h}(g)|g\rangle \\&={\frac {1}{\sqrt {|H||G|}}}\sum _{g\in G}\chi _{g}(s)\left(\sum _{h\in H}\chi _{g}(h)\right)|g\rangle \\&={\sqrt {\frac {|H|}{|G|}}}\sum _{\chi _{g}\in H^{\perp }}\chi _{g}(s)|g\rangle \end{aligned}}}</annotation>

</semantics>

</math></span></span>For the last equality, we use the following identity:

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .math_theorem{margin:1em 2em;padding:0.5em 1em 0.4em;border:1px solid #aaa;overflow:hidden}@media(max-width:500px){.mw-parser-output .math_theorem{margin:1em 0em;padding:0.5em 0.5em 0.4em}}

/* end https://en.wikipedia.org/ */

</style><div class="math_theorem" style="">

<p><strong class="theorem-name">Theorem</strong><span class="theoreme-tiret">—</span><span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{h\in H}\chi _{g}(h)={\begin{cases}|H|&\chi _{g}\in H^{\perp }\\0&\chi _{g}\notin H^{\perp }\end{cases}}}">

</mrow>

</munder>

<msub>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

</mrow>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{h\in H}\chi _{g}(h)={\begin{cases}|H|&\chi _{g}\in H^{\perp }\\0&\chi _{g}\notin H^{\perp }\end{cases}}}</annotation>

</semantics>

</math></span></span>

</p>

</div><style data-mw-deduplicate="TemplateStyles:r1174254338">

/* start https://en.wikipedia.org/ */

.mw-parser-output .math_proof{border:thin solid #aaa;margin:1em 2em;padding:0.5em 1em 0.4em}@media(max-width:500px){.mw-parser-output .math_proof{margin:1em 0;padding:0.5em 0.5em 0.4em}}

/* end https://en.wikipedia.org/ */

</style><div class="math_proof" style=""><strong>Proof</strong>

<p>This can be derived from the orthogonality of characters. The characters of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math></span><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"></span> form an orthonormal basis:<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{\vert H\vert }}\sum _{h\in H}\chi _{g}(h)\chi _{g'}(h)={\begin{cases}1&g=g'\\0&g\neq g'\end{cases}}}">

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

<msup>

</msup>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

<msup>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<msup>

</msup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {1}{\vert H\vert }}\sum _{h\in H}\chi _{g}(h)\chi _{g'}(h)={\begin{cases}1&g=g'\\0&g\neq g'\end{cases}}}</annotation>

</semantics>

</math></span></span>We let <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \chi _{g'}}">

<msub>

<msup>

</msup>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \chi _{g'}}</annotation>

</semantics>

</math></span><img src="./df9929e5944ec3d6442c007365f8a95efc146939.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.01ex; height:2.343ex;" alt="{\displaystyle \chi _{g'}}" loading="lazy"></span> be the trivial representation, which maps all inputs to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math></span><img src="./92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"></span>, to get<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{h\in H}\chi _{g}(h)={\begin{cases}\vert H\vert &g{\text{ is trivial}}\\0&g{\text{ is not trivial}}\end{cases}}}">

</mrow>

</munder>

<msub>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

<mtext> is trivial</mtext>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<mtext> is not trivial</mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{h\in H}\chi _{g}(h)={\begin{cases}\vert H\vert &g{\text{ is trivial}}\\0&g{\text{ is not trivial}}\end{cases}}}</annotation>

</semantics>

</math></span></span>Since the summation is done over <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math></span><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"></span>, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \chi _{g}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \chi _{g}}</annotation>

</semantics>

</math></span><img src="./8595db4f4f9996382ca32d7b86b5744ec29deb56.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.476ex; height:2.343ex;" alt="{\displaystyle \chi _{g}}" loading="lazy"></span> also being trivial only matters for if it is trivial over <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math></span><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"></span>; that is, if <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \chi _{g}\in H^{\perp }}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \chi _{g}\in H^{\perp }}</annotation>

</semantics>

</math></span><img src="./d32a93c0d1f098f77377ba1e658b296da0376b9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.931ex; height:3.343ex;" alt="{\displaystyle \chi _{g}\in H^{\perp }}" loading="lazy"></span>. Thus, we know that the summation will result in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \vert H\vert }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \vert H\vert }</annotation>

</semantics>

</math></span><img src="./0986f81daca0d41bcfcdc2fd60de72616afb7ef4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.357ex; height:2.843ex;" alt="{\displaystyle \vert H\vert }" loading="lazy"></span> if <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \chi _{g}\in H^{\perp }}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \chi _{g}\in H^{\perp }}</annotation>

</semantics>

</math></span><img src="./d32a93c0d1f098f77377ba1e658b296da0376b9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.931ex; height:3.343ex;" alt="{\displaystyle \chi _{g}\in H^{\perp }}" loading="lazy"></span> and will result in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math></span><img src="./2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"></span> if <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \chi _{g}\notin H^{\perp }}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \chi _{g}\notin H^{\perp }}</annotation>

</semantics>

</math></span><img src="./110f701d12af4ac23e53be92977b038a9f349aef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.931ex; height:3.343ex;" alt="{\displaystyle \chi _{g}\notin H^{\perp }}" loading="lazy"></span>.

</p>

</div>

<p>Each measurement of the final state will result in some information gained about <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math></span><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"></span> since we know that <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \chi _{g}(h)=1}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \chi _{g}(h)=1}</annotation>

</semantics>

</math></span><img src="./b9593da1e22ab18e53db321903f5e85e7999049e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:9.886ex; height:3.009ex;" alt="{\displaystyle \chi _{g}(h)=1}" loading="lazy"></span> for all <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h\in H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h\in H}</annotation>

</semantics>

</math></span><img src="./675a79e26028d91d97f4e2ce279c314b0f194c1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.243ex; height:2.176ex;" alt="{\displaystyle h\in H}" loading="lazy"></span>. <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math></span><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"></span>, or a generating set for <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math></span><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"></span>, will be found after a polynomial number of measurements. The size of a generating set will be logarithmically small compared to the size of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math></span><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"></span>. Let <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math></span><img src="./ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy"></span> denote a generating set for <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math></span><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"></span>, meaning <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \langle T\rangle =H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \langle T\rangle =H}</annotation>

</semantics>

</math></span><img src="./a92964b0fcfeb9b22f14705fe64d64c214d5e66f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.608ex; height:2.843ex;" alt="{\displaystyle \langle T\rangle =H}" loading="lazy"></span>. The size of the subgroup generated by <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math></span><img src="./ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy"></span> will at least be doubled when a new element <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t\notin T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t\notin T}</annotation>

</semantics>

</math></span><img src="./96ef5615b5fdb09585fd65cbe05883c29e301d48.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.317ex; height:2.676ex;" alt="{\displaystyle t\notin T}" loading="lazy"></span> is added to it, because <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math></span><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t+H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t+H}</annotation>

</semantics>

</math></span><img src="./d3317b23bbb672b508f1ad17b4396513897ffd98.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.744ex; height:2.343ex;" alt="{\displaystyle t+H}" loading="lazy"></span> are disjoint and because <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H\cup t+H\subseteq \langle \{t\}\cup T\rangle }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H\cup t+H\subseteq \langle \{t\}\cup T\rangle }</annotation>

</semantics>

</math></span><img src="./35d00e52f3c552fddf180ef0d64e04eb83184a08.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.681ex; height:2.843ex;" alt="{\displaystyle H\cup t+H\subseteq \langle \{t\}\cup T\rangle }" loading="lazy"></span>. Therefore, the size of a generating set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |T|}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |T|}</annotation>

</semantics>

</math></span><img src="./073a0b1ce9d4c91f30329289adbb91aae47f87ea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.93ex; height:2.843ex;" alt="{\displaystyle |T|}" loading="lazy"></span> satisfies<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |T|\leq \log |H|\leq \log |G|}">

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |T|\leq \log |H|\leq \log |G|}</annotation>

</semantics>

</math></span></span>Thus a generating set for <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math></span><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"></span> will be able to be obtained in polynomial time even if <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math></span><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"></span> is exponential in size.

</p>

<div class="mw-heading mw-heading3"><h3 id="Instances">Instances</h3></div>

<p>Many algorithms where quantum speedups occur in quantum computing are instances of the hidden subgroup problem. The following list outlines important instances of the HSP, and whether or not they are solvable.

</p>

</caption>

<th>Problem

</th>

<th>Quantum Algorithm

</th>

<th>Abelian?

</th>

<th>Polynomial time solution?

</th></tr>

<tr>

<td><a href="Deutsch%E2%80%93Jozsa_algorithm" title="Deutsch–Jozsa algorithm">Deutsch's problem</a>

</td>

<td>Deutsch's algorithm; Deutsch-Jozsa algorithm

</td>

<td>Yes

</td>

<td>Yes

</td></tr>

<tr>

<td><a href="Simon's_problem" title="Simon's problem">Simon's problem</a>

</td>

<td>Simon's algorithm

</td>

<td>Yes

</td>

<td>Yes

</td></tr>

<tr>

<td>Order finding

</td>

<td>Shor's order finding algorithm

</td>

<td>Yes

</td>

<td>Yes

</td></tr>

<tr>

<td>Discrete logarithm

</td>

<td><a href="Shor's_algorithm#Shor's_algorithm_for_discrete_logarithms" title="Shor's algorithm">Shor's algorithm § Shor's algorithm for discrete logarithms</a>

</td>

<td>Yes

</td>

<td>Yes

</td></tr>

<tr>

<td>Period finding

</td>

<td>Shor's algorithm

</td>

<td>Yes

</td>

<td>Yes

</td></tr>

<tr>

<td>Abelian stabilizer

</td>

<td>Kitaev's algorithm<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</td>

<td>Yes

</td>

<td>Yes

</td></tr>

<tr>

<td>Graph Isomorphism

</td>

<td>None

</td>

<td>No

</td>

<td>No

</td></tr>

<tr>

<td>Shortest vector problem

</td>

<td>None

</td>

<td>No

</td>

<td>No

</td></tr></tbody></table>

<ul><li><a href="Hidden_shift_problem" title="Hidden shift problem">Hidden shift problem</a></li>

<li><a href="Pontryagin_duality" title="Pontryagin duality">Pontryagin duality</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFMark_EttingerPeter_Høyer1999" class="citation arxiv cs1">Mark Ettinger; Peter Høyer (1999). "A quantum observable for the graph isomorphism problem". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/9901029">quant-ph/9901029</a></span>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFOded_Regev2003" class="citation arxiv cs1">Oded Regev (2003). "Quantum computation and lattice problems". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/cs/0304005">cs/0304005</a></span>.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFMark_EttingerPeter_HoyerEmanuel_Knill2004" class="citation journal cs1">Mark Ettinger; Peter Hoyer; Emanuel Knill (2004). "The quantum query complexity of the hidden subgroup problem is polynomial". <i>Information Processing Letters</i>. <b>91</b>: <span class="nowrap">43–</span>48. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/0401083">quant-ph/0401083</a></span>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2004quant.ph..1083E">2004quant.ph..1083E</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.ipl.2004.01.024">10.1016/j.ipl.2004.01.024</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:5520617">5520617</a>.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFKitaev1995" class="citation arxiv cs1">Kitaev, Alexei (November 20, 1995). "Quantum measurements and the Abelian Stabilizer Problem". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/9511026">quant-ph/9511026</a></span>.</cite></span>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/0012084">Richard Jozsa: Quantum factoring, discrete logarithms and the hidden subgroup problem</a></li>

<li><a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/0411037">Chris Lomont: The Hidden Subgroup Problem - Review and Open Problems</a></li>

<li><a rel="nofollow" class="external text" href="http://xstructure.inr.ac.ru/x-bin/theme2.py?arxiv=quant-ph&level=1&index1=14486">Hidden subgroup problem on arxiv.org</a></li>

<li><a rel="nofollow" class="external text" href="https://short.classiq.io/discrete_log">Complete implementation of Shor's algorithm for finding discrete logarithms with Classiq</a></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Quantum_information_science667" style="padding:3px"><table class="nowraplinks hlist mw-collapsible mw-collapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Quantum_information_science667" style="font-size:114%;margin:0 4em"><a href="Quantum_information_science" title="Quantum information science">Quantum information science</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="DiVincenzo's_criteria" title="DiVincenzo's criteria">DiVincenzo's criteria</a></li>

<li><a href="Quantum_computing" title="Quantum computing">Quantum computing</a>

<ul><li><a href="Timeline_of_quantum_computing_and_communication" title="Timeline of quantum computing and communication">timeline</a></li></ul></li>

<li><a href="Quantum_information" title="Quantum information">Quantum information</a></li>

<li><a href="Quantum_programming" title="Quantum programming">Quantum programming</a></li>

<li><a href="Quantum_simulator" title="Quantum simulator">Quantum simulation</a></li>

<li><a href="Qubit" title="Qubit">Qubit</a>

<ul><li><a href="Physical_and_logical_qubits" title="Physical and logical qubits">physical vs. logical</a></li></ul></li>

<li><a href="List_of_quantum_processors" title="List of quantum processors">Quantum processors</a>

<ul><li><a href="Cloud-based_quantum_computing" title="Cloud-based quantum computing">cloud-based</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Theorems</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Eastin%E2%80%93Knill_theorem" title="Eastin–Knill theorem">Eastin–Knill</a></li>

<li><a href="Gleason's_theorem" title="Gleason's theorem">Gleason's</a></li>

<li><a href="Gottesman%E2%80%93Knill_theorem" title="Gottesman–Knill theorem">Gottesman–Knill</a></li>

<li><a href="Holevo's_theorem" title="Holevo's theorem">Holevo's</a></li>

<li><a href="No-broadcasting_theorem" title="No-broadcasting theorem">No-broadcasting</a></li>

<li><a href="No-cloning_theorem" title="No-cloning theorem">No-cloning</a></li>

<li><a href="No-communication_theorem" title="No-communication theorem">No-communication</a></li>

<li><a href="No-deleting_theorem" title="No-deleting theorem">No-deleting</a></li>

<li><a href="No-hiding_theorem" title="No-hiding theorem">No-hiding</a></li>

<li><a href="No-teleportation_theorem" title="No-teleportation theorem">No-teleportation</a></li>

<li><a href="Quantum_speed_limit_theorems" class="mw-redirect" title="Quantum speed limit theorems">Quantum speed limit</a></li>

<li><a href="Threshold_theorem" title="Threshold theorem">Threshold</a></li>

<li><a href="Solovay%E2%80%93Kitaev_theorem" title="Solovay–Kitaev theorem">Solovay–Kitaev</a></li>

<li><a href="Schr%C3%B6dinger%E2%80%93HJW_theorem" class="mw-redirect" title="Schrödinger–HJW theorem">Schrödinger-HJW</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Quantum<br>communication</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Classical_capacity" title="Classical capacity">Classical capacity</a>

<ul><li><a href="Entanglement-assisted_classical_capacity" title="Entanglement-assisted classical capacity">entanglement-assisted</a></li>

<li><a href="Quantum_capacity" title="Quantum capacity">quantum capacity</a></li></ul></li>

<li><a href="Entanglement_distillation" title="Entanglement distillation">Entanglement distillation</a></li>

<li><a href="Entanglement_swapping" title="Entanglement swapping">Entanglement swapping</a></li>

<li><a href="Monogamy_of_entanglement" title="Monogamy of entanglement">Monogamy of entanglement</a></li>

<li><a href="Quantum_channel" title="Quantum channel">Quantum channel</a>

<ul><li><a href="Quantum_network" title="Quantum network">quantum network</a></li></ul></li>

<li><a href="Quantum_state_purification" title="Quantum state purification">State purification</a></li>

<li><a href="Quantum_teleportation" title="Quantum teleportation">Quantum teleportation</a>

<ul><li><a href="Quantum_energy_teleportation" title="Quantum energy teleportation">quantum energy teleportation</a></li>

<li><a href="Quantum_gate_teleportation" title="Quantum gate teleportation">quantum gate teleportation</a></li></ul></li>

<li><a href="Superdense_coding" title="Superdense coding">Superdense coding</a></li></ul>

</div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Quantum_cryptography24" scope="row" class="navbox-group" style="width:1%"><a href="Quantum_cryptography" title="Quantum cryptography">Quantum cryptography</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Post-quantum_cryptography" title="Post-quantum cryptography">Post-quantum cryptography</a></li>

<li><a href="Quantum_coin_flipping" title="Quantum coin flipping">Quantum coin flipping</a></li>

<li><a href="Quantum_money" title="Quantum money">Quantum money</a></li>

<li><a href="Quantum_key_distribution" title="Quantum key distribution">Quantum key distribution</a>

<li><a href="List_of_quantum_key_distribution_protocols" title="List of quantum key distribution protocols">other protocols</a></li></ul></li>

<li><a href="Quantum_secret_sharing" title="Quantum secret sharing">Quantum secret sharing</a></li></ul>

</div></td></tr></tbody></table><div>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quantum_algorithm" title="Quantum algorithm">Quantum algorithms</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Algorithmic_cooling" title="Algorithmic cooling">Algorithmic cooling</a></li>

<li><a href="Amplitude_amplification" title="Amplitude amplification">Amplitude amplification</a></li>

<li><a href="Bernstein%E2%80%93Vazirani_algorithm" title="Bernstein–Vazirani algorithm">Bernstein–Vazirani</a></li>

<li><a href="Boson_sampling" title="Boson sampling">Boson sampling</a></li>

<li><a href="Deutsch%E2%80%93Jozsa_algorithm" title="Deutsch–Jozsa algorithm">Deutsch–Jozsa</a></li>

<li><a href="Grover's_algorithm" title="Grover's algorithm">Grover's</a></li>

<li><a href="Magic_state_distillation" title="Magic state distillation">Magic state distillation</a></li>

<li><a href="Quantum_annealing" title="Quantum annealing">Quantum annealing</a></li>

<li><a href="Quantum_counting_algorithm" title="Quantum counting algorithm">Quantum counting</a></li>

<li><a href="Quantum_Fourier_transform" title="Quantum Fourier transform">Quantum Fourier transform</a></li>

<li><a href="Quantum_optimization_algorithms" title="Quantum optimization algorithms">Quantum optimization</a></li>

<li><a href="Quantum_phase_estimation_algorithm" title="Quantum phase estimation algorithm">Quantum phase estimation</a></li>

<li><a href="Simon's_problem" title="Simon's problem">Simon's</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quantum_complexity_theory" title="Quantum complexity theory">Quantum<br>complexity theory</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="PostBQP" title="PostBQP">PostBQP</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Quantum <br> processor benchmarks</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Quantum_supremacy" title="Quantum supremacy">Quantum supremacy</a></li>

<li><a href="Quantum_volume" title="Quantum volume">Quantum volume</a></li>

<li><a href="Randomized_benchmarking" title="Randomized benchmarking">Randomized benchmarking</a>

<li><a href="Relaxation_(NMR)" title="Relaxation (NMR)">Relaxation times</a>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Quantum<br><a href="Model_of_computation" title="Model of computation">computing models</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Adiabatic_quantum_computation" title="Adiabatic quantum computation">Adiabatic quantum computation</a></li>

<li><a href="Continuous-variable_quantum_information" title="Continuous-variable quantum information">Continuous-variable quantum information</a></li>

<li><a href="One-way_quantum_computer" title="One-way quantum computer">One-way quantum computer</a>

<ul><li><a href="Cluster_state" title="Cluster state">cluster state</a></li></ul></li>

<li><a href="Quantum_circuit" title="Quantum circuit">Quantum circuit</a>

<ul><li><a href="Quantum_logic_gate" title="Quantum logic gate">quantum logic gate</a></li></ul></li>

<li><a href="Quantum_machine_learning" title="Quantum machine learning">Quantum machine learning</a>

<ul><li><a href="Quantum_neural_network" title="Quantum neural network">quantum neural network</a></li></ul></li>

<li><a href="Quantum_Turing_machine" title="Quantum Turing machine">Quantum Turing machine</a></li>

<li><a href="Topological_quantum_computer" title="Topological quantum computer">Topological quantum computer</a></li>

<li><a href="Hamiltonian_quantum_computation" title="Hamiltonian quantum computation">Hamiltonian quantum computation</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quantum_error_correction" title="Quantum error correction">Quantum<br>error correction</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li>Codes

<ul><li><a href="Five-qubit_error_correcting_code" title="Five-qubit error correcting code">5 qubit</a></li>

<li><a href="Quantum_convolutional_code" title="Quantum convolutional code">quantum convolutional</a></li>

<li><a href="Stabilizer_code" title="Stabilizer code">stabilizer</a></li>

<li><a href="Bacon%E2%80%93Shor_code" title="Bacon–Shor code">Bacon–Shor</a></li>

<li><a href="Steane_code" title="Steane code">Steane</a></li>

<li><a href="Toric_code" title="Toric code">Toric</a></li>

<li><a href="Entanglement-assisted_stabilizer_formalism" title="Entanglement-assisted stabilizer formalism">Entanglement-assisted</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Physical<br>implementations</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quantum_optics" title="Quantum optics">Quantum optics</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Cavity_quantum_electrodynamics" title="Cavity quantum electrodynamics">Cavity QED</a></li>

<li><a href="Circuit_quantum_electrodynamics" title="Circuit quantum electrodynamics">Circuit QED</a></li>

<li><a href="Linear_optical_quantum_computing" title="Linear optical quantum computing">Linear optical QC</a></li>

<li><a href="KLM_protocol" title="KLM protocol">KLM protocol</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Ultracold_atom" title="Ultracold atom">Ultracold atoms</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Neutral_atom_quantum_computer" title="Neutral atom quantum computer">Neutral atom QC</a></li>

<li><a href="Trapped-ion_quantum_computer" title="Trapped-ion quantum computer">Trapped-ion QC</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Spin_(physics)" title="Spin (physics)">Spin</a>-based</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Spin_qubit_quantum_computer" title="Spin qubit quantum computer">Spin qubit QC</a></li>

<li><a href="Nitrogen-vacancy_center" title="Nitrogen-vacancy center">NV center</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Superconducting_quantum_computing" title="Superconducting quantum computing">Superconducting</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Charge_qubit" title="Charge qubit">Charge qubit</a></li>

<li><a href="Flux_qubit" title="Flux qubit">Flux qubit</a></li>

<li><a href="Phase_qubit" title="Phase qubit">Phase qubit</a></li>

<li><a href="Transmon" title="Transmon">Transmon</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quantum_programming" title="Quantum programming">Quantum<br>programming</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="OpenQASM" title="OpenQASM">OpenQASM</a>–<a href="Qiskit" title="Qiskit">Qiskit</a>–<a href="IBM_Quantum_Experience" class="mw-redirect" title="IBM Quantum Experience">IBM QX</a></li>

<li><a href="Quil_(instruction_set_architecture)" title="Quil (instruction set architecture)">Quil</a>–<a href="Rigetti_Computing" title="Rigetti Computing">Forest/Rigetti QCS</a></li>

<li><a href="Libquantum" title="Libquantum">libquantum</a></li>

<li><a href="Quantum_programming" title="Quantum programming">many others...</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li><span class="noviewer" typeof="mw:File"><span title="Category"></span></span> Quantum information science</li>

<li><span class="noviewer" typeof="mw:File"><span title="Template"></span></span> Quantum mechanics topics</li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-03-26" href="https://en.wikipedia.org/wiki/?title=Hidden_subgroup_problem&oldid=1282445874">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>